import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/9 22:23
 * @description 抽象为分组背包问题，每一个骰子为一组，枚举组 - 枚举容量 - 枚举决策
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.numRollsToTarget(2, 6, 7);
    }
    int mod = (int)1e9+7;
    public int numRollsToTarget(int n, int m, int t) {
        // 去掉 物品维度，利用01背包模型，进行一维空间优化
        // f[j]表示 得到点数 j的方案数
        int[] f = new int[t + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            // 将目标点数从大到小进行遍历
            for (int j = t; j >= 0; j--) {
                // 每一次累加前置为零
                f[j] = 0;
                for (int k = 1; k <= m; k++) {
                    if (j >= k) {
                        f[j] = (f[j] + f[j-k]) % mod;
                    }
                }
            }
        }
        return f[t];
    }
}
